package leetcode.linkedlist;

import java.util.Stack;

public class PalindromeLinkedList234 {

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    class Solution1 {
        public boolean isPalindrome(ListNode head) {
            Stack<Integer> stack = new Stack<>();
            ListNode temp = head;
            while (temp != null) {
                stack.push(temp.val);
                temp = temp.next;
            }
            while (head != null) {
                if (stack.pop() != head.val) {
                    return false;
                }
                head = head.next;
            }
            return true;
        }
    }

    class Solution2 {
        public boolean isPalindrome(ListNode head) {
            if (head == null || head.next == null) {
                return true;
            }
            ListNode fast = head;
            ListNode slow = head;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            slow = slow.next;
            ListNode pre = null;
            while (slow != null) {
                ListNode next = slow.next;
                slow.next = pre;
                pre = slow;
                slow = next;
            }
            while (pre != null) {
                if (head.val != pre.val) {
                    return false;
                }
                pre = pre.next;
            }
            return true;
        }
    }
}
